package toOffer;

/**
 * <h3>leetcode</h3>
 *
 * @author BigFaceCat
 * @date 2024/1/28 15:47
 * @description <p>展平多级双向链表 </p>
 */
public class toOffer4_5_28 {
    public static void main(String[] args) {
//        List<Integer> head = List.of(1, 2, 3, 4, null, null, 5, 6, 7, null, null, 8, 9);
        Node node1 = new Node(1, null, null, null);
        Node node2 = new Node(2, node1, null, null);
        node1.next = node2;
        Node node3 = new Node(3, node2, null, null);
        node2.next = node3;
        Node node4 = new Node(4, node3, null, null);
        node3.next = node4;

        Node node5 = new Node(5, null, null, null);
        node2.child = node5;
        Node node6 = new Node(6, node5, null, null);
        node5.next = node6;
        Node node7 = new Node(7, node6, null, null);
        node6.next = node7;

        Node node8 = new Node(8, null, null, null);
        node6.child = node8;
        Node node9 = new Node(9, node8, null, null);
        node8.next = node9;

        Node head = node1;
        Node node = flatten(head);
        while (node != null){
            System.out.print(node.val + " ");
            node = node.next;
        }
    }

    /**
     * 思想：
     * 如果一个节点，它又有next、又有child，
     * 可以找一个temp指向child，然后把temp展平后，再把next展平，
     * 最后把child节点删除、把next拼接到temp后面。
     * @param head
     * @return
     */
    public static Node flatten(Node head) {
        //判空
        if (head == null){
            return null;
        }
        //递归
        Node currNext = flatten(head.next);
        Node currChild = flatten(head.child);
        Node temp = currChild;
        //把child节点调整成next节点
        if (currChild != null){
            head.next = currChild;
            currChild.prev = head;
        }
        //遍历子节点，找到里面的最后一个不为空的节点
        while (temp != null && temp.next != null){
            temp = temp.next;
        }
        //连接child和next节点
        if (temp != null && currNext != null){
            temp.next = currNext;
            currNext.prev = temp;
        }
        //删除child节点
        head.child = null;
        return head;
    }

    /**
     * @param head
     * @return
     */
    public static Node flatten1(Node head) {
        flattenGetTail(head);
        return head;
    }

    /**
     * @param head
     * @return
     */
    public static Node flattenGetTail(Node head) {
        Node node = head;
        Node tail = null;
        while (node != null) {
            Node next = node.next;
            if (node.child != null) {
                Node child = node.child;
                Node childTail = flattenGetTail(node.child);

                node.child = null;
                node.next = child;
                child.prev = node;
                childTail.next = next;
                if (next != null) {
                    next.prev = childTail;
                }

                tail = childTail;
            } else {
                tail = node;
            }
            node = next;
        }
        return tail;
    }

    private static class Node {
        public int val;
        public Node prev;
        public Node next;
        public Node child;

        public Node(int val, Node prev, Node next, Node child) {
            this.val = val;
            this.prev = prev;
            this.next = next;
            this.child = child;
        }

        public Node() {
        }
    }
}
